package Lee_code;

import java.util.ArrayDeque;
import java.util.Deque;

public class Lee_234 {

     public class ListNode {
         int val;
         ListNode next;

         ListNode() {
         }

         ListNode(int val) {
             this.val = val;
         }

         ListNode(int val, ListNode next) {
             this.val = val;
             this.next = next;
         }
     }

    public boolean isPalindrome(ListNode head) {

        if (head == null || head.next == null) return true;
        int count = 0;
        ListNode temp = head;

        while (temp != null) {
            count++;
            temp = temp.next;
        }
        System.out.println(count);
        if(count % 2 != 0)
            return false;

        Deque<ListNode> deque = new ArrayDeque<>();
        temp = head;
        for(int i=0; i<count; i++){
            if (i<count/2) {
                deque.push(temp);
            }
            else {
                if(deque.peek() != temp)
                    return false;
                deque.pop();
            }
            temp = temp.next;
        }
        return true;
    }
}
